class Solution {
private:
    // 单调队列
    class MQueue{
    public:
        deque<int> q;  // 双端队列
      //如果val大于队尾元素数值，那么从队尾出队直到val <= 队头元素数值为止。
      // 这样就保持了队列里的数值是单调从大到小的了。
        void push(int val){
            while(!q.empty() && val > q.back()){
                q.pop_back();
            }  
            q.push_back(val);
        }
        // 如果窗口移除的元素val等于单调队列的出口元素，那么队列弹出元素，否则不用操作
        void pop(int val){
            if(!q.empty() && val == q.front()) 
                q.pop_front();
        }
        int maxnum(){
            return q.front();
        }
    };

public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ret;  // 返回的滑动窗口最值
        MQueue mq;  // 单调队列

        // 将前 K 个元素放入窗口
        for(int i = 0; i < k; ++i)
            mq.push(nums[i]);
        ret.push_back(mq.maxnum());  // 记录第一个窗口最值
        // 窗口滑动
        for(int i = k; i < nums.size(); ++i){
            mq.pop(nums[i-k]);
            mq.push(nums[i]);
            ret.push_back(mq.maxnum());  // 记录最值
        }

        return ret;
    }
};